퍼셉트론은 가장 단순하고 빠른 판별 함수 기반 분류 모형이지만 판별 경계선(decision hyperplane)이 유니크하게 존재하지 않는다는 특징이 있다.
서포트 벡터 머신(SVM: support vector machine)은 퍼셉트론 기반의 모형에 가장 안정적인 판별 경계선을 찾기 위한 제한 조건을 추가한 모형이라고 볼 수 있다.
서포트 벡터 머신의 장점과 단점은 다음과 같다.
장점:
단점:
판별 함수 $f(z) = f(w^Tx-w_0)$ 를 가지는 판별 함수 기반 모형의 판별 경계선은 다음과 같이 주어진다.
$$ w^T x - w_0 = 0 $$이 수식은 경계선에서 0이 된다는 조건만 지키면 되기 때문에 가장 가까운 클래스 +1의 표본 데이터 $x^{+}$과 가장 가까운 클래스 -1의 표본 데이터 $x^{-}의 값이 각각 1과 -1이 되도록 스케일링(scaling)할 수 있다.
$$ w^T x^{+} - w_0 = +1 $$$$ w^T x^{-} - w_0 = -1 $$이 판별 경계선과 표본 데이터 $x^{+}$, $x^{-}$ 사이의 거리는 다음과 같이 주어진다.
$$ \dfrac{w^T x^{+} - w_0}{\| w \|} $$$$ -\dfrac{w^T x^{-} - w_0}{\| w \|} $$[[school_notebook:dd1680bfbaab414a8d54dc978c6e883a]]
이 거리의 합을 마진(margin)이라고 하며 마진값이 클 수록 더 경계선이 안정적이라고 볼 수 있다. 그런데 위에서 정한 스케일링에 의해 마진은 다음과 같이 정리된다.
$$ \dfrac{w^T x^{+} - w_0}{\| w \|} -\dfrac{w^T x^{-} - w_0}{\| w \|} = \dfrac{2}{\| w \|}$$마진 값이 최대가 되는 경우는 $\| w \|$ 즉, $\| w \|^2$가 최소가 되는 경우와 같다.
즉, 서포트 벡터 머신은 값을 최소화 하면서 모든 표본 데이터에 대해 다음 조건을 만족해야 한다.
$$ y \cdot \hat{y} = y \cdot( w^Tx - w_o)\geq 1 $$$$ y \cdot ( w^Tx - w_o) - 1 \geq 0$$Karush–Kuhn–Tucker 조건을 사용하면 최소화 목적 함수를 다음과 같이 고치면 된다.
$$ L = \dfrac{1}{2} ||w||^2 - \sum_{n=1}^N a_n (y_n \cdot ( w^Tx_n - w_o) - 1 ) $$위 함수를 $w$, $w_0$ 로 미분하여 기울기가 0이되는 조건을 구하면 다음과 같다.
$$ w = \sum_{n=1}^N a_n y_n x_n $$$$ 0 = \sum_{n=1}^N a_n y_n $$이 조건을 대입하여 $w$, $w_0$을 없애면 다음과 같은 문제가 된다.
$$ L = \sum_{n=1}^N a_n - \dfrac{1}{2}\sum_{n=1}^N\sum_{m=1}^N a_n a_m y_n y_m x_n^T x_m $$이 때 $a$는 다음 조건을 만족한다. $$ \sum_{n=1}^N a_n y_n = 0, \;\;\; a_n \geq 0 $$
이 문제는 $w$를 구하는 문제가 아니라 $a$를 구하는 문제로 바뀌었으므로 dual form 이라고도 한다.
dual form 문제는 수치적으로 Box 제한 조건이 있는 이차 프로그래밍 문제(quadratic programming)가 되므로 적은 연산량으로 풀 수 있다.
dual form 문제를 풀어 함수 $L$ 를 최소화하는 $a$를 구하면 예측 모형을 다음과 같이 쓸 수 있다.
$$ y = w^T x - w_0 = \sum_{n=1}^N a_n y_n x_n^T x - w_0 $$이차 프로그래밍(최적화)로 구한 $a_n = 0$ 이면 해당 데이터는 예측 모형, 즉 $w$ 계산에 아무런 기여를 하지 않는다는 것을 알 수 있다.
만약 $n$번째 데이터에 대해 $a_n > 0$ 이면 조건 만족을 위해 $y_n(w^Tx_n - w_o) = 1$이 된다. 즉 판별함수 값 $w^Tx_n - w_o = \pm 1$ 이다.
이러한 데이터를 서포트(support)라고 한다.
In [1]:
from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=50, centers=2, random_state=4, cluster_std=0.60)
xmin = X[:,0].min()
xmax = X[:,0].max()
ymin = X[:,1].min()
ymax = X[:,1].max()
xx = np.linspace(xmin, xmax, 10)
yy = np.linspace(ymin, ymax, 10)
X1, X2 = np.meshgrid(xx, yy)
def plot_svm(model):
Z = np.empty(X1.shape)
for (i, j), val in np.ndenumerate(X1):
x1 = val
x2 = X2[i, j]
p = model.decision_function([[x1, x2]])
Z[i, j] = p[0]
levels = [-1.0, 0.0, 1.0]
linestyles = ['dashed', 'solid', 'dashed']
plt.scatter(X[:, 0], X[:, 1], c=y, s=100, cmap=plt.cm.Paired)
plt.contour(X1, X2, Z, levels, colors='k', linestyles=linestyles)
plt.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], s=150, linewidth=3, facecolors='none')
plt.show()
from sklearn.svm import SVC
model = SVC(kernel='linear').fit(X, y)
plot_svm(model)
In [2]:
x_new = [10, 2]
model.decision_function([x_new])
Out[2]:
In [3]:
model.coef_.dot(x_new) + model.intercept_
Out[3]:
In [4]:
model.support_vectors_
Out[4]:
In [5]:
model.support_
Out[5]:
In [6]:
y[model.support_]
Out[6]:
In [7]:
# dual_coef_ = y_i \alpha_i
model.dual_coef_[0][0] * model.support_vectors_[0].dot(x_new) + \
model.dual_coef_[0][1] * model.support_vectors_[1].dot(x_new) + \
model.intercept_
Out[7]:
In [8]:
y[model.support_][1]
Out[8]:
In [9]:
model.n_support_
Out[9]:
만약 데이터가 직선인 판별 경계선으로 나누어지지 않는 즉, 선형 분리(linear separable)가 불가능 한 경우에는 다음과 같이 슬랙 변수(slack variable)를 사용하여 개별적인 오차를 허용할 수 있다.
원래 판별 함수의 값은,
클래스 $+1$ 영역의 샘플 $x_{+}$에 대해
$$ w^Tx_{+} - w_0 \geq 1 $$클래스 $-1$ 영역의 샘플 $x_{-}$에 대해
$$ w^Tx_{-} - w_0 \leq -1 $$이어야 한다.
양수인 슬랙 변수 $\xi \geq 0 $를 사용하면 이 조건을 다음과 같이 완화할 수 있다.
$$ w^Tx_{+} - w_0 \geq +1-\xi_i $$$$ w^Tx_{-} - w_0 \leq -1+\xi_i $$$$ \xi \geq 0 $$대신 슬랙 변수의 크기를 제한해야 하므로 위의 부등식 조건을 모두 고려한 최적화 목적 함수는 다음과 같아진다.
$$ L = \dfrac{1}{2} ||w||^2 - \sum_{n=1}^N a_n (y_n \cdot ( w^Tx_n - w_o) - 1 + \xi_n ) - \sum_{n=1}^N \mu_n \xi_n + C \sum_{n=1}^N \xi_n $$
In [10]:
np.random.seed(0)
X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]
Y = [0] * 20 + [1] * 20
fignum = 1
for name, penalty in (('C=1', 1), ('C=0.05', 0.05)):
clf = SVC(kernel='linear', C=penalty).fit(X, Y)
w = clf.coef_[0]
a = -w[0] / w[1]
xx = np.linspace(-5, 5)
yy = a * xx - (clf.intercept_[0]) / w[1]
margin = 1 / np.sqrt(np.sum(clf.coef_ ** 2))
yy_down = yy + a * margin
yy_up = yy - a * margin
plt.figure(fignum)
x_min = -5
x_max = 5
y_min = -9
y_max = 9
XX, YY = np.mgrid[x_min:x_max:200j, y_min:y_max:200j]
Z = clf.predict(np.c_[XX.ravel(), YY.ravel()])
Z = Z.reshape(XX.shape)
plt.contourf(XX, YY, Z, cmap=plt.cm.Accent, alpha=0.6)
plt.plot(xx, yy, 'k-')
plt.plot(xx, yy_down, 'k--')
plt.plot(xx, yy_up, 'k--')
plt.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1], s=120, linewidth=4, facecolors='none')
plt.scatter(X[:, 0], X[:, 1], c=Y, s=60, linewidth=1, cmap=plt.cm.Paired)
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
plt.xticks(())
plt.yticks(())
plt.title(name)
plt.axis('tight')
plt.show()
fignum = fignum + 1;
In [16]:
from sklearn.datasets import fetch_olivetti_faces
faces = fetch_olivetti_faces()
N=2; M=5;
np.random.seed(0)
fig = plt.figure(figsize=(9,5))
plt.subplots_adjust(top=1, bottom=0, hspace=0, wspace=0.05)
klist = np.random.choice(range(len(faces.data)), N * M)
for i in range(N):
for j in range(M):
k = klist[i*M+j]
ax = fig.add_subplot(N, M, i*M+j+1)
ax.imshow(faces.images[k], cmap=plt.cm.bone);
ax.grid(False)
ax.xaxis.set_ticks([])
ax.yaxis.set_ticks([])
plt.title(faces.target[k])
plt.tight_layout()
plt.show()
In [17]:
from sklearn.cross_validation import train_test_split
X_train, X_test, y_train, y_test = train_test_split(faces.data, faces.target, test_size=0.25, random_state=0)
In [18]:
from sklearn.svm import SVC
svc_1 = SVC(kernel='linear').fit(X_train, y_train)
In [20]:
fig = plt.figure(figsize=(3,30))
for i, k in enumerate(np.random.choice(len(y_test), 10)):
ax = fig.add_subplot(10, 1, i + 1)
ax.imshow(X_test[k:(k+1), :].reshape(64,64), cmap=plt.cm.bone);
ax.grid(False)
ax.xaxis.set_ticks([])
ax.yaxis.set_ticks([])
plt.title("actual %d => predict %d" % (y_test[k], svc_1.predict(X_test[k:(k+1), :])[0]))
plt.tight_layout()
plt.show()
In [22]:
glasses = [
( 10, 19), ( 30, 32), ( 37, 38), ( 50, 59), ( 63, 64),
( 69, 69), (120, 121), (124, 129), (130, 139), (160, 161),
(164, 169), (180, 182), (185, 185), (189, 189), (190, 192),
(194, 194), (196, 199), (260, 269), (270, 279), (300, 309),
(330, 339), (358, 359), (360, 369)
]
def create_target(segments):
y = np.zeros(faces.target.shape[0])
for (start, end) in segments:
y[start:end + 1] = 1
return y
target_glasses = create_target(glasses)
X_train, X_test, y_train, y_test = train_test_split(faces.data, target_glasses, test_size=0.25, random_state=0)
In [23]:
svc_2 = SVC(kernel='linear').fit(X_train, y_train)
In [25]:
fig = plt.figure(figsize=(3,30))
for i, k in enumerate(np.random.choice(len(y_test), 10)):
ax = fig.add_subplot(10, 1, i + 1)
ax.imshow(X_test[k:(k+1), :].reshape(64,64), cmap=plt.cm.bone);
ax.grid(False)
ax.xaxis.set_ticks([])
ax.yaxis.set_ticks([])
plt.title("prediction: %s" % ("glasses" if (svc_2.predict(X_test[k:(k+1), :])[0]) else "no glasses"))
plt.tight_layout()
plt.show()